package isSubsequence;

public class Solution {
    public boolean isSubsequence(String s, String t) {
        // 双指针
//        int i = 0,j = 0;
//        while (i<s.length()) {
//            boolean find = false;
//            while (j<t.length()) {
//                if(s.charAt(i)!=t.charAt(j))j++;
//                else {
//                    j++;
//                    find = true;
//                    break;
//                }
//            }
//            if(!find)return false;
//            i++;
//        }
//        return i == s.length();

        // 动态规划
        // dp[i][j]第i个字符开始往后 字符j 第一次出现的位置
        // dp[i][j] = s[i] == j+'a'?i:dp[i+1][j].
        int m = s.length(),n = t.length();
        if(n == 0) {
            return m == 0;
        }
        int[][] dp = new int[n][26];
        for (int i = n-1; i >= 0; i--) {
            for (int j = 0; j < 26; j++) {
                if(t.charAt(i) == j+'a') {
                    dp[i][j] = i;
                } else {
                    // 两种情况 第一 该位置是在字符串的末尾 如果在末尾的话就表明没有
                    if( i == n-1 ) {
                        dp[i][j] = -1;
                    } else {
                        dp[i][j] = dp[i+1][j];
                    }
                }
            }
        }
        // 比较字符串 每次都要找到已经匹配的字符的下一个字符的位置
        int add = 0;
        for (int i = 0; i < s.length(); i++) {
            if(add>=n)return false;
            if(dp[add][s.charAt(i)-'a'] == -1) {
                return false;
            }
            add = dp[add][s.charAt(i)-'a']+1;
        }
        return true;
    }
}
